package _12;

/**
 * @author ：Rwto
 * @date ：Created in 2021/7/23 10:20
 * @description：矩阵中的路径
 */
public class Solution {
    public boolean exist(char[][] board, String word) {

        char[] chars = word.toCharArray();
        int n = board.length;
        int m = board[0].length;
        for(int i = 0;i<n;i++){
            for(int j = 0; j< m; j++){
                if(board[i][j]==chars[0]){
                    if(dfs(board,i,j,chars,0)){
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] word, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, i + 1, j,word,  k + 1) || dfs(board, i - 1, j, word, k + 1) ||
                dfs(board, i, j + 1, word, k + 1) || dfs(board,  i , j - 1, word,k + 1);
        board[i][j] = word[k];

        return res;

    }



    public static void main(String[] args) {



    }
}
